package fun.ticsmyc.question.dp;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.question.dp
 * @date 2021-02-06 12:23
 */
public class 股票买卖 {

    /**
     * 不限交易次数
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int n = prices.length;

        int[][] dp = new int[n][2];
        dp[0][0] = - prices[0];
        for(int i=1;i<dp.length;++i){
            dp[i][0] = Math.max(dp[i-1][1]-prices[i] , dp[i-1][0]);
            dp[i][1]= Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[n-1][1];
    }

    /**
     * 卖出后有一天冷冻期
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {
        int n = prices.length;
        if(n ==0){
            return 0;
        }
        int[][] dp = new int[n][2];
        dp[0][0]=-prices[0];

        for(int i=1;i<n;++i){
            dp[i][0]= (i>=2 ?Math.max(dp[i-1][0],dp[i-2][1]-prices[i]) : Math.max(dp[i-1][0], -prices[i]));
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[n-1][1];
    }

    /**
     * 带手续费
     * @param prices
     * @param fee
     * @return
     */
    public int maxProfit(int[] prices, int fee) {
        int  n = prices.length;
        if(n ==0) return 0;

        int[][] dp = new int[n][2];
        dp[0][0] = - prices[0];

        for(int i=1; i<n;++i){
            dp[i][0]= Math.max(dp[i-1][0], dp[i-1][1]-prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);
        }
        return dp[n-1][1];

    }

    /**
     * 交易k次
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if(n==0) return 0;
        int[][][] dp = new int[n][k+1][2];
        for(int i=1;i<=k;++i){
            dp[0][i][0] = -prices[0];
        }

        int max =0;
        for(int i=1;i<n;++i){
            for(int j=1;j<=k;++j){
                dp[i][j][0] = Math.max(dp[i-1][j][0],dp[i-1][j-1][1]-prices[i]);  //持有
                dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j][0]+prices[i]);
                max =Math.max(max,dp[i][j][1]);
            }
        }
        return max;
    }
}
